#include <iostream>

const int capacity = 10;

class MaxHeap
{
public:
    MaxHeap() : size(0) {}
    void Insert(int value)
    {
        if (size == capacity)
            return;
        array[size] = value;
        SifwUp(size); // 上浮
        size++;
    }

    // 只能删除根
    void Remove() // 根和要删的互换，删完之后再下沉    // 时间复杂度：log(n)
    {
        if (size == 0)
            return;
        // array[0]  = array[size - 1]; 
        // size--;
        array[0] = array[--size];  // 不用交换，直接将值拿给根  (上面两句合并)  因为将根删完之后会找不到新的根，所以需要将这个值赋值给根
        SiftDown(0);
    }

    int *GetRoot() // 取根(只能取根)
    {
        if (size == 0)
            return nullptr;
        return &array[0];
    }

    void show()
    {
        for (int i = 0; i < size; i++)
        {
            std::cout << array[i] << " ";
        }
        std::cout << std::endl;
    }

private:
    int GetParent(int i) { return (i - 1) / 2; } // 获取双亲结点下标 
    int GetLeftChild(int i) { return 2 * i + 1; }
    int GetRightChild(int i) { return 2 * i + 2; }

    void SifwUp(int i) // 上浮       // log(n)(走树的高度)
    {
        while (i > 0 && array[i] > array[GetParent(i)]) // 保证有根(i > 0)
        {
            std::swap(array[i], array[GetParent(i)]);
            i = GetParent(i); // 我上浮之后还要继续向前走, 循环上浮
        }
    }

    void SiftDown(int i) // 下沉操作，跟左右孩子比，找三个里面最大的，然后跟它换位置
    {
        int left = GetLeftChild(i);
        int right = GetRightChild(i);

        int max = i; //
        if (left < size && array[left] > array[max])    // left < size:保证左孩子一定存在
        {
            max = left;
        }
        if (right < size && array[right] > array[max])
        {
            max = right;
        }
        if (max != i) // i下沉了
        {
            std::swap(array[i], array[max]);
            SiftDown(max); // 递归下沉；为什么用递归，可以用循环吗
        }
    }

    int array[capacity];
    int size;
};

int main()
{
    MaxHeap h;
    for (int i = 0; i < 10; i++)
    {
        h.Insert(i + 1);
    }
    h.show();

    h.Remove();
    h.show();
}
